//伪代码
//首先也是像上面一样去掉全部的边，每个节点都是一个组件（森林）
//对于每个组件（森林）都找其相邻权重最小的边，将这些边添加到组件上，不断重复直到所有的节点都能被访问
//这里对添加的边要做一个是否构成环的判断
import GraphVertex from '../res/data-structures/graph/GraphVertex.js';
import GraphEdge from '../res/data-structures/graph/GraphEdge.js';
import Graph from '../res/data-structures/graph/Graph.js';
let flag=true;
export default function Boruvka(graphList,edgeTreeList) {
    let visited = []
    //n个最小生成树
    let MST = graphList;
    console.log(graphList);
    console.log(edgeTreeList);
    flag=true;
    while (flag) {
        for (let i=0;i<MST.length;i++) {
            let obj= findSmallestEdge(MST[i],edgeTreeList);
            if(obj==null) break;
            let {smallestEdge,toVertice}=obj;
             i=combineGraph(MST,i,toVertice,smallestEdge);
            visited.push(smallestEdge);
            // 合并某些组件
        }
    }
    console.log(visited);
    return visited;
}
function findSmallestEdge(graph,edgeTreeList){
    let edges=edgeTreeList;
    let edgesList=[];
    let vertices=graph.vertices;
    let smallWeight=100000;
    let smallestEdge;
    let toVertice;
    //遍历子树的所有顶点与 所有边 找到最短的边
    for(let obj in vertices){
        for(let o in edges){
            //如果已经在图中的跳过继续搜索
            if(
                graph.getVertexByKey(edges[o].startVertex.value)&&graph.getVertexByKey(edges[o].endVertex.value)
              ) continue;
            if(edges[o].startVertex.value==vertices[obj].value){
                if(edges[o].weight<smallWeight){
                    smallWeight=edges[o].weight;
                    smallestEdge=edges[o];
                    toVertice=edges[o].endVertex;
                }
            }
            if(edges[o].endVertex.value==vertices[obj].value){
                if(edges[o].weight<smallWeight){
                    smallWeight=edges[o].weight;
                    smallestEdge=edges[o];
                    toVertice=edges[o].startVertex;
                }
            }
       }
    }
    if(smallWeight==100000) {flag=false;return null;}
    else return {smallestEdge,toVertice};
}
function combineGraph(MST,index,toVertice,smallestEdge){
    let combineIndex=-1;
    for(let i=0;i<MST.length;i++){
        for(let o in MST[i].vertices){
           if(MST[i].vertices[o].value==toVertice.value){
               combineIndex=i;break;
           }
        }
    }
    if(combineIndex!=-1){
        let edges=MST[combineIndex].getAllEdges();
        for(let o in edges){
            MST[index].addEdge(edges[o]);
        }
        let vertices=MST[combineIndex].getAllVertices()
         for(let o in vertices){
            MST[index].addVertex(vertices[o]);
        }
        MST[index].addEdge(smallestEdge);
        MST.splice(combineIndex,1);
        console.log(MST);
        if(combineIndex<index) return index-1;
        else return index;
    }
    else{
        console.log("error");
    }
}